package leetcode.code0732;

public class MyCalendarThree {

//	当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。
//
//	给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。
//
//	实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。
//
//	MyCalendarThree() 初始化对象。
//	int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

	private final int MAX = (int) 1e9 + 1;

	private class Node {
		public int lazy;
		public int k;
		public Node left;
		public Node right;
	}

	private Node root;

	public MyCalendarThree() {
		this.root = new Node();
	}

	public int book(int start, int end) {
		this.add(start + 1, end, 1, MAX, root);
		int ans = this.query(start + 1, end, 1, MAX, root);
		return ans;
	}

	private int query(int L, int R, int l, int r, Node root) {
		return root.k;
	}

	private void add(int L, int R, int l, int r, Node root) {
		if (L <= l && r <= R) {
			root.lazy += 1;
			root.k += 1;
			return;
		}
		if (root.left == null) {
			root.left = new Node();
		}
		if (root.right == null) {
			root.right = new Node();
		}
		pushDown(root);
		int mid = ((r - l) >> 1) + l;
		if (R <= mid) {
			this.add(L, R, l, mid, root.left);
		} else if (L > mid) {
			this.add(L, R, mid + 1, r, root.right);
		} else {
			this.add(L, R, l, mid, root.left);
			this.add(L, R, mid + 1, r, root.right);
		}
		root.k = Math.max(root.left.k, root.right.k);
	}

	private void pushDown(Node root) {
		if (root.lazy != 0) {
			root.left.lazy += root.lazy;
			root.left.k += root.lazy;
			root.right.lazy += root.lazy;
			root.right.k += root.lazy;
			root.lazy = 0;
			root.k = 0;
		}
	}

	public static void main(String[] args) {
		MyCalendarThree myCalendarThree = new MyCalendarThree();
		myCalendarThree.print(myCalendarThree, 10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
		myCalendarThree.print(myCalendarThree, 50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
		myCalendarThree.print(myCalendarThree, 10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
		myCalendarThree.print(myCalendarThree, 5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
		myCalendarThree.print(myCalendarThree, 5, 10); // 返回 3
		myCalendarThree.print(myCalendarThree, 25, 55); // 返回 3

//		myCalendarThree.print(myCalendarThree, 10, 15); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
//		myCalendarThree.print(myCalendarThree, 14, 17); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
	}

	private void print(MyCalendarThree myCalendarThree, int start, int end) {
		int ans = myCalendarThree.book(start, end);
		System.out.println(ans);
	}

//	["MyCalendarThree","book","book","book","book","book","book"]
//	[[],[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]]
}
